package com.qf.arith;

/**
 * 约瑟夫环
 *
 *   n:变量   算法：规模    量有多大？
 *   O(n)
 *
 *
 * @author lixu
 */
public class TestYueSeFu {

    //一个人   共41个人
    ///双向链表
    static class Node<E> {
        E value;
        Node<E> next;//后继
        Node<E> prov; //前驱

        public Node(E value) {
            this.value = value;
        }
    }

    //空间复杂度O(1)  时间复杂度O(1)
    public static void main(String[] args) {//   O(1278) ~O(1)
        //环 圆
        //环 ： 头
        Node<Integer> top = new Node<>(1);//第一个人
        //临时
        Node<Integer> p = top;

        //25 36 37 38 39 41 1
        for (int i = 2; i <= 41; i++) {// 除了第一个人以外：后面的40个人  4*40=160
            //2~40的时候
            if (p.next == null) {
                p.next = new Node<Integer>(i);
                //将后一个链表的前驱指向了前一个链表的地址
                p.next.prov = p;
                //将临时节点向下移动
                p = p.next;
            }
        }
        //p=41节点的地址
        //首与尾相连
        p.next=top;
        top.prov=p;

        //临时p 首节点
        p = top;  //O(n)  一行代码算  空间复杂度

        //循环遍历
        for (int i = 0; i < 41; i++) {
            System.out.print(p.value + " ");
            p = p.next;
        }

        System.out.println();
        //杀人游戏开始  1-2-3-4-....41-1-2-3....          16(约瑟夫）-  31（他的朋友）

        int i = 1;
        while (true){
            if(p.next==p){
                //最后一个人了
                System.out.print(p.value + " ");
                break;
            }
            if(i%3==0){
                //杀死之前 留下遗言
                System.out.print(p.value + " ");
                p.prov.next=p.next;
                p.next.prov=p.prov;
                i=1;
            }else{
                i++;
            }
            //移动
            p=p.next;
        }




       /* int i = 1; // 1 2 3  1 2 3
        while (true){
            //还有人 要继续杀
            if(i%3==0){
                if(p.next==p){
                    System.out.print(p.value + " ");
                    break;
                }
                //
                System.out.print(p.value + " ");
                //杀死  p
                p.prov.next=p.next;
                p.next.prov=p.prov;
                //人一旦死了 报数就从1开始重报了
                i=1;
            }else{
                i++;
            }
            //移动
            p=p.next;//

        }*/
        //没有人了

    }
}
